
"""
定义 dp[i] 为以 i 结束的最长有效括号长度。
状态转移方程：

1.s[i] == ‘(’
dp[i] = 0
2.s[i] == ‘)’
    a. s[i-1] == ‘(’: dp[i] = dp[i-2] + 2
    例如：()()
    b. s[i-1] == ‘)’ and s[i - 1 - dp[i-1]] == ‘(’: dp[i] = dp[i-1] + dp[i - 1 - dp[i-1] - 1] + 2
    例如：()(())
注意数组越界情况。

"""

def longestValidParentheses(s):
    # 获取字符串 s 的长度
    n = len(s)
    # 初始化结果变量，用于记录最长有效括号子串的长度
    res = 0
    # 初始化 dp 数组，长度为 n，初始值都为 0
    dp = [0] * n
    # 遍历字符串 s 中的每个字符
    for i in range(n):
        # 获取当前字符
        c = s[i]
        # 如果当前字符是左括号 '('，则以它结尾的子串不可能是有效括号子串，所以 dp[i] 为 0
        if c == '(':
            dp[i] = 0
        else:
            #()()
            # 情况 1：如果当前字符是右括号 ')'，且前一个字符是左括号 '('
            if i > 0 and s[i - 1] == '(':
                # 如果 i 大于 1，说明前面还有字符，当前有效括号子串的长度等于 dp[i - 2] 的长度加上 2（当前的左右括号对）
                if i > 1:
                    dp[i] = dp[i - 2] + 2
                # 如果 i 等于 1，说明前面只有一个字符，当前有效括号子串的长度就是 2
                else:
                    dp[i] = 2

            # ()(())
            # 情况 2：如果当前字符是右括号 ')'，且前一个字符也是右括号 ')'
            elif i > 0 and s[i - 1] == ')':
                # 检查是否存在与当前右括号匹配的左括号 dp[i-1]为前i-1 已经配对的长度
                if i - 1 - dp[i - 1] >= 0 and s[i - 1 - dp[i - 1]] == '(':
                    # 如果匹配的左括号前面还有字符
                    if i - 1 - dp[i - 1] - 1 >= 0:
                        # ()(())
                        # 当前有效括号子串的长度等于 前一个有效括号子串的长度加上 2（当前匹配的左右括号对），再加上匹配左括号前面的有效括号子串的长度(最前面的一对())
                        dp[i] = dp[i - 1] + 2 + dp[i - 1 - dp[i - 1] - 1]
                    # 如果匹配的左括号前面没有字符
                    else:
                        # (())
                        # 当前有效括号子串的长度等于前一个有效括号子串的长度加上 2（当前匹配的左右括号对）
                        dp[i] = dp[i - 1] + 2
        # 更新最长有效括号子串的长度
        res = max(res, dp[i])
    # 返回最长有效括号子串的长度
    return res

# 方法二： 栈
def longestValidParentheses(s):
    # 初始化一个栈，栈底初始元素为 -1，用于辅助计算有效括号子串的长度
    stack = [-1]
    # 初始化结果变量，用于记录最长有效括号子串的长度
    res = 0
    # 遍历字符串 s，同时获取每个字符的索引 i 和字符 c
    for i, c in enumerate(s):
        # 如果当前字符是左括号 '('
        if c == '(':
            # 将当前字符的索引压入栈中
            stack.append(i)
        # 如果当前字符是右括号 ')'
        else:
            # 检查栈顶元素是否不为 -1 且栈顶元素对应的字符是左括号 '('
            if stack[-1] != -1 and s[stack[-1]] == '(':
                # 弹出栈顶元素，即匹配的左括号的索引
                stack.pop()
                # 计算当前有效括号子串的长度
                # 当前索引 i 减去栈顶元素（即上一个未匹配的字符的索引），得到当前有效括号子串的长度
                res = max(res, i - stack[-1])
            # 如果栈顶元素对应的字符不是左括号或者栈顶元素是 -1
            else:
                # 将当前右括号的索引压入栈中
                stack.append(i)
    # 返回最长有效括号子串的长度
    return res

